package com.wc.data_structures.linkedlist;

/**
 * @Author congge
 * @Date 2023/4/19 18:57
 * @description 双向链表
 */
public class DoubleLinkedListDemo {
}

class DoubleLinkedList<T> {
    // 虚拟头指针
    private final DoubleLinkedNode<T> head;
    // 虚拟尾指针
    private final DoubleLinkedNode<T> rear;

    public DoubleLinkedList() {
        head = new DoubleLinkedNode<>();
        rear = new DoubleLinkedNode<>();
        head.right = rear;
        rear.left = head;
    }

    public DoubleLinkedNode<T> getHead() {
        return head;
    }

    public DoubleLinkedNode<T> getRear() {
        return rear;
    }

    /**
     * 将该节点删除
     *
     * @param node
     */
    public void deleteNode(DoubleLinkedNode<T> node) {
        node.left.right = node.right;
        node.right.left = node.left;
    }

    /**
     * 在node1 后面 添加node2
     *
     * @param node1
     * @param node2
     */
    public void addNode(DoubleLinkedNode<T> node1, DoubleLinkedNode<T> node2) {
        node2.right = node1.right;
        node2.left = node1;
        node1.right.left = node2;
        node1.right = node2;
    }
}

class DoubleLinkedNode<T> {
    public T value;

    public DoubleLinkedNode<T> left;

    public DoubleLinkedNode<T> right;

    public DoubleLinkedNode() {

    }

    public DoubleLinkedNode(T value, DoubleLinkedNode<T> left, DoubleLinkedNode<T> right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}
